import offer.TreeNode;

/**
 * @Author: wangliuyang
 * @Date: 2021/9/7 19:39
 * @Description:
 */
public class Solution_105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        return buildtree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildtree(int[] preorder, int start, int end, int[] inorder, int left, int right) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new TreeNode(preorder[start]);
        }
        int temp = preorder[start];
        int i = left;
        for (; i <= right; i++) {
            if (inorder[i] == temp) {
                break;
            }
        }
        TreeNode node = new TreeNode(temp);
        node.left = buildtree(preorder, start + 1, start + i - left, inorder, left, i - 1);
        node.right = buildtree(preorder, start + i - left + 1, end, inorder, i + 1, right);
        return node;
    }
}
